package br.ufrrj.im.redes.logic;

import java.security.SecureRandom;


public abstract class NumberTheory {

	
	static public final boolean PRIME = true;
	static public final boolean COMPOSITE = false;

	static public final boolean WITNESS = true;
	static public final boolean NOWITNESS = false;

	// probabily precision of a number be prime
	static public final int PRECISION = 50;

	
	// Algorithm Modular-Exponentiation: d = a^b mod n
	static public Long modularExponentiation(long a, long b, long n) {

		long d;
		String binaryStringOfb;
		int l;
		
		d = 1;
		l = (int) (Math.log(b) / Math.log(2));
		binaryStringOfb = Long.toBinaryString(b);
	
		
		for(int i = 0; i <= l; i++) {
			
			d = mod(d*d, n); // d = d^2 mod n

			if (binaryStringOfb.charAt(i) == '1') // if b_i == 1
				d = mod(d*a, n); // d = d*a mod n
		}

		return d;
	}
	
	//Function to compute a mod b
	public static long mod(long a, long b)
	{

		long r = a % b;
		
		/*
		The operator '%' of the Java considers remains negative,
		which iradicts our definition, so if r = a % b
		is negative return r + b, otherwise it returns r.
		*/

		return (r < 0 ? r + b : r);
	}


	// Verify if a is a witness to compositness of n or if a^(n-1) mod n != 1
	static public boolean witness(long a, long n) {

		long q = n - 1;
		int k = 0;
		long x[]; 
		int i; //the counter
	
		
		//write n - 1 = 2^kq
		do
		{
			q = q >> 1; //shift right bits q
			k += 1;

		} while (q % 2 == 0); //verify if the last bit of q is 1.

		x = new long[k+1];

		//x_0 = x^q mod n
		x[0] = modularExponentiation(a, q, n);

		for (i = 1; i <= k; i++)
		{
			x[i] = ((long)Math.pow(x[i-1], 2)) % n; //x_i = x_(i-1)^2 mod n
			
			//if a is witness for composite of n
			if ((x[i] == 1) && (x[i-1] != 1) && (x[i-1] != n-1)) 
				return WITNESS;
		}
		
		//if a^(n-1) mod n != 1
		if (x[k] != 1)
			return WITNESS;
		
		return NOWITNESS; //a not is witness for composite of n and a^(n-1) mod n = 1
	}

	// Probabilistic primality test due Miller and Rabin
	static public boolean millerRabinPrimalityTest(long n, int s) {
		long a;

		for (int i = 1; ((i <= s) && (i < n)); i++) {
			a = (Math.abs(new SecureRandom().nextLong()) % (n-1)) + 1;
			//System.out.println("a: " + a);

			if (witness(a, n) == WITNESS)
				return COMPOSITE; // Certainly
		}

		return PRIME; // Almost surely
	}
	
	static public long generateRandomValue(int min, long max){
		return ((new SecureRandom().nextLong()) % max) + min;
	}
	
	

}
